#include <bits/stdc++.h>

#ifdef LLT_DBG
#define FR freopen("in.txt", "r", stdin)
#else
#define FR
#endif

using namespace std;
using ll = long long;

const ll mod = 167772161;
const ll g = 3;

const int FACT_SIZE = 262145;
ll fact[FACT_SIZE];
ll inv_fact[FACT_SIZE];

template <ll P>
ll fpow(ll a, ll b)
{
    assert((a != 0 || b != 0) && b >= 0);
    ll res = 1;
    for (; b; b >>= 1, a = (a * a) % P)
        if (b & 1)
            res = (res * a) % P;
    return res;
}

void init_fact()
{
    fact[0] = 1;
    for (int i = 1; i < FACT_SIZE; i++)
        fact[i] = fact[i - 1] * i % mod;
    inv_fact[FACT_SIZE - 1] = fpow<mod>(fact[FACT_SIZE - 1], mod - 2);
    for (int i = FACT_SIZE - 2; i >= 0; i--)
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod;
}

int align2(int n)
{
    int E = 0;
    int i = 1;
    while (i < n)
    {
        E++;
        i <<= 1;
    }
    return E;
}

/**
 * @brief NTT 计算器
 *
 * @tparam G 原根
 * @tparam P 模数
 * @tparam AT 输入数组类型
 */
template <ll G, ll P, typename AT>
class NTT
{
private:
    int _n;
    shared_ptr<ll[]> rev;

    static NTT<G, P, AT> _singletons[32];

    /**
     * @brief 迭代 NTT
     *
     * @param A 输入数组
     * @param k 单位根系数
     */
    void _rNTT(AT A, ll k) const
    {
        for (int i = 0; i < (1 << _n); i++)
            if (i < rev[i])
                swap(A[i], A[rev[i]]);

        for (int e = 1; e <= _n; e++)
        {
            int m = 1 << e;
            ll gn = fpow<P>(G, ((P - 1) / m * k) % (P - 1));
            for (int i = 0; i < (1 << _n); i += m)
            {
                int hf = m / 2;
                ll g = 1;
                for (int j = 0; j < hf; j++)
                {
                    ll x = A[i + j];
                    ll y = (A[i + j + hf] * g) % P;
                    A[i + j] = (x + y) % P;
                    A[i + j + hf] = (x - y) % P;
                    g = (g * gn) % P;
                }
            }
        }
    }

public:
    /**
     * @brief 构建一个空 NTT 计算器
     *
     */
    NTT() : _n(0), rev() {}
    /**
     * @brief 构建一个 NTT 计算器
     *
     * @param n 多项式最高项数长度
     */
    NTT(int n) : _n(n), rev(new ll[1 << n])
    {
        // 初始化逆位置对换
        rev[0] = 0;
        for (int i = 1; i < (1 << n); i++)
            rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (n - 1));
    }

    /**
     * @brief 获取 NTT 单例对象
     *
     * @param n 多项式最高项数长度
     * @return NTT<G, P> NTT 单例对象
     */
    static NTT<G, P, AT> getSingleton(int n)
    {
        if (!NTT<G, P, AT>::_singletons[n].rev)
            NTT<G, P, AT>::_singletons[n] = NTT<G, P, AT>(n);

        return NTT<G, P, AT>::_singletons[n];
    }

    /**
     * @brief NTT 过程
     *
     * @param A 系数数组
     */
    void doNTT(AT A) const
    {
        _rNTT(A, 1);
    }

    /**
     * @brief NTT 逆过程
     *
     * @param A 点值数组
     */
    void doINTT(AT A) const
    {
        ll ni = fpow<P>(1 << _n, P - 2);
        _rNTT(A, P - 2);
        for (int i = 0; i < (1 << _n); i++)
            A[i] = (A[i] * ni) % P;
    }
};

template <ll G, ll P, typename AT>
NTT<G, P, AT> NTT<G, P, AT>::_singletons[32];

/**
 * @brief NTT 多项式
 *
 * @tparam G 原根
 * @tparam P 模数
 */
template <ll G, ll P>
class Poly
{
private:
    shared_ptr<ll[]> vec;
    int _n;
    int _capacity;
    bool _is_ntt;

public:
    /**
     * @brief 创建一个空引用多项式
     *
     */
    Poly() : vec(), _n(0), _capacity(0), _is_ntt(false)
    {
    }

    /**
     * @brief 创建一个空值多项式
     *
     * @param n 多项式最高项数长度
     */
    Poly(int n) : vec(new ll[1 << n]), _n(n), _capacity(n), _is_ntt(false)
    {
        for (int i = 0; i < this->size(); i++)
            (*this)[i] = 0;
    }

    /**
     * @brief 计算多项式实际长度
     *
     * @return 多项式实际长度
     */
    int size() const
    {
        return 1 << _n;
    }

    /**
     * @brief 对多项式的长度进行剪裁
     *
     * @param n 新的多项式最高项数长度
     */
    void clip(int n)
    {
        if (_is_ntt && n != _n)
            throw logic_error("Clipping will lose information in NTT state.");
        if (_capacity >= n)
        {
            // 直接扩容并清空
            if (n > _n)
                for (int i = (1 << _n); i < (1 << n); i++)
                    (*this)[i] = 0;
            _n = n;
        }
        else
        {
            // 重新分配内存扩容
            Poly<G, P> p(n);
            for (int i = 0; i < this->size(); i++)
                p[i] = (*this)[i];
            *this = p;
        }
    }

    /**
     * @brief 引用取值
     *
     * @param s 下标
     * @return 值引用
     */
    ll &operator[](int s)
    {
        return vec[s];
    }

    /**
     * @brief 取值
     *
     * @param s 下标
     * @return 值
     */
    ll operator[](int s) const
    {
        return vec[s];
    }

    /**
     * @brief 克隆多项式
     *
     * @return 克隆新的多项式
     */
    Poly<G, P> clone() const
    {
        Poly<G, P> p(_n);

        for (int i = 0; i < this->size(); i++)
            p[i] = (*this)[i];

        p._is_ntt = _is_ntt;

        return p;
    }

    /**
     * @brief 克隆多项式
     *
     * @param n 新的多项式最高项数长度
     * @return 克隆新的多项式
     */
    Poly<G, P> clone(int n) const
    {
        if (n < _n)
            throw logic_error("The length is less than the original length.");
        Poly<G, P> p(n);

        for (int i = 0; i < this->size(); i++)
            p[i] = (*this)[i];

        p._is_ntt = _is_ntt;

        return p;
    }

    /**
     * @brief 将多项式状态转换为点值
     *
     */
    void ntt()
    {
        if (_is_ntt)
            throw logic_error("Poly was already in ntt state.");
        NTT<G, P, Poly<G, P>> ntt = NTT<G, P, Poly<G, P>>::getSingleton(_n);
        ntt.doNTT(*this);
        _is_ntt = true;
    }

    /**
     * @brief 将多项式状态转换为插值
     *
     */
    void intt()
    {
        if (!_is_ntt)
            throw logic_error("Poly was not in ntt state.");
        NTT<G, P, Poly<G, P>> ntt = NTT<G, P, Poly<G, P>>::getSingleton(_n);
        ntt.doINTT(*this);

        _is_ntt = false;
    }

    /**
     * @brief 多项式相加
     *
     * @param o 右值多项式
     * @return 新的多项式
     */
    Poly<G, P> operator+(const Poly<G, P> &o) const
    {
        if (_is_ntt && o._is_ntt && _n != o._n)
            throw logic_error("Unit root length is not equal.");
        if ((_is_ntt && !o._is_ntt) || (!_is_ntt && o._is_ntt))
            throw logic_error("Poly state is different.");

        Poly<G, P> p = this->clone(max(_n, o._n));
        for (int i = 0; i < o.size(); i++)
            p[i] = (p[i] + o[i]) % P;

        return p;
    }

    /**
     * @brief 多项式原地加法
     *
     * @param o 右值多项式
     * @return 原多项式
     */
    Poly<G, P> &operator+=(const Poly<G, P> &o)
    {
        if (_is_ntt && o._is_ntt && _n != o._n)
            throw logic_error("Unit root length is not equal.");
        if ((_is_ntt && !o._is_ntt) || (!_is_ntt && o._is_ntt))
            throw logic_error("Poly state is different.");

        this->clip(max(_n, o._n));

        for (int i = 0; i < min(this->size(), o.size()); i++)
            (*this)[i] = ((*this)[i] + o[i]) % P;

        return *this;
    }

    /**
     * @brief 多项式相减
     *
     * @param o 右值多项式
     * @return 新的多项式
     */
    Poly<G, P> operator-(const Poly<G, P> &o) const
    {
        if (_is_ntt && o._is_ntt && _n != o._n)
            throw logic_error("Unit root length is not equal.");
        if ((_is_ntt && !o._is_ntt) || (!_is_ntt && o._is_ntt))
            throw logic_error("Poly state is different.");

        Poly<G, P> p = this->clone(max(_n, o._n));

        for (int i = 0; i < o.size(); i++)
            p[i] = (p[i] - o[i]) % P;

        return p;
    }

    /**
     * @brief 多项式原地减法
     *
     * @param o 右值多项式
     * @return 原多项式
     */
    Poly<G, P> &operator-=(const Poly<G, P> &o)
    {
        if (_is_ntt && o._is_ntt && _n != o._n)
            throw logic_error("Unit root length is not equal.");
        if ((_is_ntt && !o._is_ntt) || (!_is_ntt && o._is_ntt))
            throw logic_error("Poly state is different.");

        this->clip(max(_n, o._n));

        for (int i = 0; i < min(this->size(), o.size()); i++)
            (*this)[i] = ((*this)[i] - o[i]) % P;

        return *this;
    }

    /**
     * @brief 多项式乘常数
     *
     * @param v 右值
     * @return 新的多项式
     */
    Poly<G, P> operator*(ll v) const
    {
        Poly<G, P> p = this->clone();

        for (int i = 0; i < this->size(); i++)
            p[i] = (v * p[i]) % P;

        return p;
    }

    /**
     * @brief 多项式原地乘常数
     *
     * @param v 右值
     * @return 源多项式
     */
    Poly<G, P> &operator*=(ll v)
    {
        for (int i = 0; i < this->size(); i++)
            (*this)[i] = (v * (*this)[i]) % P;

        return *this;
    }

    /**
     * @brief 多项式相乘（卷积）
     *
     * @param o 多项式右值
     * @return 新的多项式
     */
    Poly<G, P> operator*(const Poly<G, P> &o) const
    {
        static vector<Poly<G, P>> bufs(32);
        if ((_is_ntt && !o._is_ntt) || (!_is_ntt && o._is_ntt))
            throw logic_error("Poly state is different.");

        if (_is_ntt && o._is_ntt)
        {
            if (_n != o._n)
                throw logic_error("Unit root length is not equal.");

            Poly<G, P> p = this->clone();

            for (int i = 0; i < this->size(); i++)
                p[i] = p[i] * o[i] % P;

            return p;
        }
        else
        {
            int nk = max(_n, o._n) + 1;
            Poly<G, P> pa = this->clone(nk);
            if (!bufs[nk].vec)
                bufs[nk] = Poly<G, P>(nk);

            bufs[nk]._is_ntt = false;
            for (int i = 0; i < o.size(); i++)
                bufs[nk][i] = o[i];

            for (int i = o.size(); i < (1 << nk); i++)
                bufs[nk][i] = 0;

            pa.ntt();
            bufs[nk].ntt();
            pa *= bufs[nk];
            pa.intt();
            return pa;
        }
    }

    /**
     * @brief 多项式原地相乘（卷积）
     *
     * @param o 多项式右值
     * @return 源多项式
     */
    Poly<G, P> &operator*=(const Poly<G, P> &o)
    {
        static vector<Poly<G, P>> bufs(32);
        if ((_is_ntt && !o._is_ntt) || (!_is_ntt && o._is_ntt))
            throw logic_error("Poly state is different.");

        if (_is_ntt && o._is_ntt)
        {
            if (_n != o._n)
                throw logic_error("Unit root length is not equal.");

            for (int i = 0; i < this->size(); i++)
                (*this)[i] = (*this)[i] * o[i] % P;

            return *this;
        }
        else
        {
            int nk = max(_n, o._n) + 1;
            this->clip(nk);
            if (!bufs[nk].vec)
                bufs[nk] = Poly<G, P>(nk);

            bufs[nk]._is_ntt = false;
            for (int i = 0; i < o.size(); i++)
                bufs[nk][i] = o[i];

            for (int i = o.size(); i < (1 << nk); i++)
                bufs[nk][i] = 0;

            this->ntt();
            bufs[nk].ntt();
            (*this) *= bufs[nk];
            (*this).intt();
            return *this;
        }
    }

    /**
     * @brief 计算多项式的乘法逆元（牛顿迭代法）
     *
     * @return 多项式的乘法逆元
     */
    Poly<G, P> inv() const
    {
        if ((*this)[0] == 0)
            throw logic_error("Inverse zero.");

        Poly<G, P> g(0);
        g[0] = fpow<P>((*this)[0], P - 2);

        for (int i = 1; i <= _n; i++)
        {
            Poly<G, P> vk(i);
            for (int j = 0; j < vk.size(); j++)
                vk[j] = (*this)[j];

            g = g * 2 - g * g * vk;
            g.clip(i);
        }

        return g;
    }

    /**
     * @brief 多形式转置
     *
     * @return 转置的多项式
     */
    Poly<G, P> transpose() const
    {
        Poly<G, P> p(_n);
        for (int i = 0; i < this->size(); i++)
            p[i] = (*this)[this->size() - i - 1];
        return p;
    }

    /**
     * @brief 多项式除法
     *
     * @param o 多项式右值
     * @return pair<商，余数>
     */
    pair<Poly<G, P>, Poly<G, P>> operator/(const Poly &o) const
    {
        Poly<G, P> ar = this->transpose();
        Poly<G, P> br = o.transpose();
        br.clip(_n - o._n + 1);
        Poly<G, P> dr = ar * br.inv();
        dr.clip(_n - o._n + 1);
        Poly<G, P> d = dr.transpose();
        Poly<G, P> r = (*this) - o * d;
        r.clip(o._n);

        return make_pair(d, r);
    }

    /**
     * @brief 多项式求导
     *
     * @return 多项式的导数
     */
    Poly<G, P> derivation() const
    {
        Poly<G, P> p(_n);
        for (int i = 1; i < this->size(); i++)
            p[i - 1] = ((*this)[i] * i) % P;
        return p;
    }

    /**
     * @brief 多项式积分
     *
     * @param c 常数
     * @return 积分多项式
     */
    Poly<G, P> integral(ll c) const
    {
        Poly<G, P> p(_n + 1);
        p[0] = c;
        for (int i = 0; i < this->size(); i++)
            p[i + 1] = ((*this)[i] * fpow<P>(i + 1, P - 2)) % P;
        return p;
    }

    /**
     * @brief 计算多项式的对数
     *
     * @return 多项式对数
     */
    Poly<G, P> ln() const
    {
        if (((*this)[0] + P) % P != 1)
            throw logic_error("Undefined logarithm.");
        Poly<G, P> p = ((*this).derivation() * (*this).inv()).integral(0);
        p.clip(_n);
        return p;
    }

    /**
     * @brief 计算多项式指数（牛顿迭代）
     *
     * @return 多项式指数
     */
    Poly<G, P> exp() const
    {
        if (((*this)[0] + P) % P != 0)
            throw logic_error("Undefined exponent.");
        Poly<G, P> g(0);
        g[0] = 1;

        for (int i = 1; i <= _n; i++)
        {
            Poly<G, P> vk(i);
            for (int j = 0; j < vk.size(); j++)
                vk[j] = (*this)[j];
            Poly<G, P> ck = vk - g.ln();
            ck[0] = (ck[0] + 1) % P;
            g = g * ck;
            g.clip(i);
        }
        return g;
    }

    /**
     * @brief 多项式快速幂
     *
     * @param k 幂
     * @return 多项式的幂
     */
    Poly<G, P> pow(ll k) const
    {
        Poly<G, P> q(_n);
        int p = -1;
        for (int i = 0; i < this->size(); i++)
        {
            if ((*this)[i] != 0)
            {
                p = i;
                break;
            }
        }

        if (p == -1)
            return Poly<G, P>(0);

        ll a = (*this)[p];
        ll ia = fpow<P>(a, P - 2);
        ll ak = fpow<P>(a, k);
        for (int i = 0; i + p < this->size(); i++)
            q[i] = (*this)[i + p] * ia % P;
        q = (q.ln() * k).exp();
        Poly<G, P> v(_n);
        for (int i = 0; i + k * p < this->size(); i++)
            v[i + k * p] = (q[i] * ak) % P;
        return v;
    }

    Poly<G, P> translation(ll k)
    {
        if (k == 0)
            return this->clone();
        Poly<G, P> pa(_n);
        Poly<G, P> pb(_n);
        for (int i = 0; i < this->size(); i++)
        {
            pa[i] = fact[i] * (*this)[i] % P;
            pb[this->size() - i - 1] = fpow<P>(k, i) * inv_fact[i] % P;
        }

        Poly<G, P> pv = pa * pb;
        Poly<G, P> ans(_n);

        for (int i = 0; i < this->size(); i++)
        {
            ans[i] = pv[i + this->size() - 1] * inv_fact[i] % P;
        }

        return ans;
    }
};